package algorithm;

public class PrimesInMillion {
	static int MAX = 1000000;
	static boolean[] notPrimes = new boolean[MAX];
	public static void main(String[] args) {
		for (int i = 2; i < MAX; i++) {
			if(i * i > MAX){
				break;
			}
			if(isPrime(i)){
				notPrimes[i] = false;
				int j = 2;
				while(j * i < MAX){
					notPrimes[j * i] = true;
					j++;
				}
			}
		}
		
		for (int i = 2; i < MAX; i++) {
			//System.out.println("------------------");
			if(notPrimes[i] == false){
				System.out.println(i);
			}
		}
		System.out.println(isPrime(999983));
		System.exit(0);
	}

	static boolean isPrime(int num) {
		if (num == 2 || num == 3) {
			return true;
		}
		if (num % 6 != 1 && num % 6 != 5) {
			return false;
		}
		for (int i = 5; i * i <= num; i += 6) {
			if (num % i == 0 || num % (i + 2) == 0) {
				return false;
			}
		}
		return true;
	}
}
